// 选择排序 先取第一个数依次与后面的数进行比较，通过minpos记录最小的索引，默认第一个最小。当遍历一遍后，就会找到最小的那个数的索引。
// 然后把第一个数和minPos对应的数进行交换;然后从第二个数开始循环...
// 时间大O：n^2

let arr = [5, 3, 6, 8, 1, 7, 9, 4, 2]
let arr2 = [5, 1, 1, 2, 0, 0]
function selectSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minPos = i
    for (let j = i + 1; j < arr.length; j++) {
      minPos = arr[j] < arr[minPos] ? j : minPos
    }
    swap(arr, i, minPos)
  }
  return arr
}

function swap(arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

console.log(selectSort(arr))
console.log(selectSort(arr2))
